package com.leetcode.algorithm.y22.m09.w3;

import com.leetcode.algorithm.common.TreeNode;

/**
 * 687. 最长同值路径
 * 
 * https://leetcode.cn/problems/longest-univalue-path/
 * 
 * @author jie.deng
 *
 */
class Question0687Solution01 {

	public int longestUnivaluePath(TreeNode root) {
		int[] resultRef = new int[] { 0 };
		dfs(root, resultRef);
		return resultRef[0];
	}

	/**
	 * 
	 * @param root
	 * @param resultRef
	 * @return 返回以root结尾的同值路径的最大长度
	 */
	private int dfs(TreeNode root, int[] resultRef) {
		if (root == null) {
			return 0;
		}

		int left = dfs(root.left, resultRef);
		int right = dfs(root.right, resultRef);
		if (root.left != null && root.left.val == root.val) {
			left++;
		} else {
			left = 0;
		}
		if (root.right != null && root.right.val == root.val) {
			right++;
		} else {
			right = 0;
		}
		if (left + right > resultRef[0]) {
			resultRef[0] = left + right;
		}
		return Math.max(left, right);
	}

}